# 

# 

# ### Hungarian算法详解与Python代码示例

# 

# #### 一、算法简介

# 

# Hungarian算法，也称为匈牙利算法，是一种在多项式时间内求解任务分配问题的组合优化算法。该算法最初由匈牙利数学家D. König提出，并由W.W. Kuhn在1955年进行了改进和推广。它主要用于解决二分图的最大匹配问题，即在一个无向图中，如果顶点集V可以分割为两个互不相交的子集X和Y，并且图中的每条边都恰好连接X中的一个顶点和Y中的一个顶点，则称该图为二分图。匈牙利算法的目标是在这样的二分图中找到边数最多的子集，即最大匹配。

# 

# #### 二、算法核心思想

# 

# 匈牙利算法的核心思想是通过寻找增广路径来逐步增加匹配中的边数。增广路径是一条从非匹配顶点出发，交替经过匹配边和非匹配边，最终到达另一个非匹配顶点的路径。通过取反增广路径上的匹配边和非匹配边，可以得到一个更大的匹配。重复这个过程，直到找不到增广路径为止，此时得到的匹配即为最大匹配。

# 

# #### 三、Python代码示例

# 

# 下面是一个使用Python实现的匈牙利算法示例：

# 

# 

def hungarian_algorithm(graph):

    """

    使用匈牙利算法求解二分图的最大匹配问题

    :param graph: 二分图的邻接矩阵，graph[i][j]表示顶点i和顶点j之间是否有边相连（1表示有边，0表示无边）

    :return: 最大匹配的边数以及匹配方案（以列表形式返回，每个元素是一个元组，表示匹配的顶点对）

    """

    # 获取二分图的顶点数

    n = len(graph)

    

    # 初始化匹配方案为空

    match = [-1] * n

    

    # 遍历所有未匹配的顶点，寻找增广路径

    for u in range(n):

        if match[u] == -1:

            if dfs(graph, match, u):

                # 找到增广路径，更新匹配方案

                pass

    

    # 统计最大匹配的边数并构建匹配方案列表

    max_edges = 0

    matching = []

    for u in range(n):

        if match[u] != -1:

            max_edges += 1

            matching.append((u, match[u]))

    

    # 返回最大匹配的边数和匹配方案

    return max_edges, matching





def dfs(graph, match, u):

    """

    深度优先搜索寻找增广路径

    :param graph: 二分图的邻接矩阵

    :param match: 当前匹配方案

    :param u: 当前搜索的顶点

    :return: 是否找到增广路径（找到返回True，未找到返回False）

    """

    # 标记当前顶点为已访问

    visited = [False] * len(graph)

    visited[u] = True

    

    # 遍历当前顶点的所有邻接顶点

    for v in range(len(graph[u])):

        if graph[u][v] and not visited[v]:

            # 如果邻接顶点v未被访问且存在边相连

            if match[v] == -1 or dfs(graph, match, match[v]):

                # 如果v是未匹配顶点，或者从v的匹配顶点出发可以找到增广路径

                match[u] = v  # 更新匹配方案

                if match[v] != -1:

                    match[match[v]] = -1  # 取反增广路径上的匹配边

                return True

    

    # 未找到增广路径

    return False



# 示例用法

graph = [

    [0, 1, 0, 1],

    [1, 0, 1, 0],

    [0, 1, 0, 1],

    [1, 0, 1, 0]

]

max_edges, matching = hungarian_algorithm(graph)

print(f"最大匹配的边数：{max_edges}")

print(f"匹配方案：{matching}")
